<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="iwLLB" id="iwLLB"><span data-lake-id="u30a1c75d" id="u30a1c75d">典型回答</span></h1>
  <p data-lake-id="uf05ff175" id="uf05ff175"><br></p>
  <p data-lake-id="u53ff8279" id="u53ff8279"><span data-lake-id="u5b216f17" id="u5b216f17">hash方法的功能是根据Key来定位这个K-V在链表数组中的位置的。也就是hash方法的输入应该是个Object类型的Key，输出应该是个int类型的数组下标。</span></p>
  <p data-lake-id="uf520d6cf" id="uf520d6cf"><br></p>
  <p data-lake-id="u923d4ab9" id="u923d4ab9"><span data-lake-id="uce6877a8" id="uce6877a8">最简单的话，我们只要调用Object对象的hashCode()方法，该方法会返回一个整数，然后用这个数对HashMap或者HashTable的容量进行取模就行了。只不过，在具体实现上，考虑到效率等问题，HashMap的实现会稍微复杂一点。他的具体实现主要由两个方法int hash(Object k)和int indexFor(int h, int length)来实现的（JDK 1.8中不再单独有indexFor方法，但是在计算具体的table index时也用到了一样的算法逻辑，具体代码可以看putVal方法）。</span></p>
  <p data-lake-id="uccc7babf" id="uccc7babf"><span data-lake-id="u34212316" id="u34212316">​</span><br></p>
  <blockquote data-lake-id="u5a50220e" id="u5a50220e">
   <p data-lake-id="u2c7554fb" id="u2c7554fb"><span data-lake-id="u91d7fede" id="u91d7fede">hash ：该方法主要是将Object转换成一个整型。</span></p>
   <p data-lake-id="uf2bd3a0a" id="uf2bd3a0a"><span data-lake-id="u6ebf212f" id="u6ebf212f">indexFor ：该方法主要是将hash生成的整型转换成链表数组中的下标。</span></p>
  </blockquote>
  <p data-lake-id="udcbc76ce" id="udcbc76ce"><span data-lake-id="u8e8a81c1" id="u8e8a81c1">​</span><br></p>
  <p data-lake-id="u835f1fbe" id="u835f1fbe"><span data-lake-id="u3032fb2a" id="u3032fb2a">在这里面，HashMap的hash方法为了提升效率，主要用到了以下技术手段：</span></p>
  <p data-lake-id="ua7417059" id="ua7417059"><span data-lake-id="u47395083" id="u47395083">​</span><br></p>
  <p data-lake-id="uc5dce788" id="uc5dce788"><span data-lake-id="u8e380b41" id="u8e380b41">1、</span><strong><span data-lake-id="uc5110865" id="uc5110865">使用位运算(&amp;)来代替取模运算(%)</span></strong><span data-lake-id="u8245287c" id="u8245287c">，因为位运算(&amp;)效率要比代替取模运算(%)高很多，主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。</span></p>
  <p data-lake-id="u7d9e1c47" id="u7d9e1c47"><span data-lake-id="ubda134a5" id="ubda134a5">2、对hashcode进行</span><strong><span data-lake-id="u5fbb3efb" id="u5fbb3efb">扰动计算</span></strong><span data-lake-id="ua6860b79" id="ua6860b79">，防止不同hashCode的高位不同但低位相同导致的hash冲突。简单点说，就是为了把高位的特征和低位的特征组合起来，降低哈希冲突的概率，也就是说，尽量做到任何一位的变化都能对最终得到的结果产生影响。</span></p>
  <h1 data-lake-id="kObUn" id="kObUn"><span data-lake-id="ue069ca5d" id="ue069ca5d">扩展知识</span></h1>
  <p data-lake-id="u6871c0c6" id="u6871c0c6"><br></p>
  <h2 data-lake-id="Otb1y" id="Otb1y"><span data-lake-id="uccf3f393" id="uccf3f393">使用&amp;代替%运算</span></h2>
  <p data-lake-id="u27f0cadd" id="u27f0cadd"><br></p>
  <p data-lake-id="u07b32657" id="u07b32657"><span data-lake-id="u02bbf010" id="u02bbf010">不知道，大家有没有想过，为什么可以使用位运算(&amp;)来实现取模运算(%)呢？</span></p>
  <p data-lake-id="u8f408b36" id="u8f408b36"><span data-lake-id="uabd508dd" id="uabd508dd">​</span><br></p>
  <p data-lake-id="u540940c8" id="u540940c8"><span data-lake-id="ua5c45cf6" id="ua5c45cf6">这实现的原理如下：</span></p>
  <p data-lake-id="ucadc7e66" id="ucadc7e66"><br></p>
  <blockquote data-lake-id="u98a5eb38" id="u98a5eb38">
   <p data-lake-id="ud2af4625" id="ud2af4625"><span data-lake-id="u07070a83" id="u07070a83">X % 2^n = X &amp; (2^n - 1)</span></p>
   <p data-lake-id="u56b07be2" id="u56b07be2"><span data-lake-id="u59708e86" id="u59708e86"> </span></p>
   <p data-lake-id="u9a0f371e" id="u9a0f371e"><span data-lake-id="u70073e44" id="u70073e44">2^n表示2的n次方，也就是说，一个数对2^n取模 == 一个数和(2^n - 1)做按位与运算 。</span></p>
   <p data-lake-id="u88c7acf4" id="u88c7acf4"><span data-lake-id="ud8c1ccfe" id="ud8c1ccfe"> </span></p>
   <p data-lake-id="u9d6e34cb" id="u9d6e34cb"><span data-lake-id="u0a4fdf32" id="u0a4fdf32">假设n为3，则2^3 = 8，表示成2进制就是1000。2^3 -1 = 7 ，即0111。</span></p>
   <p data-lake-id="ud8c73e05" id="ud8c73e05"><span data-lake-id="u7d365248" id="u7d365248"> </span></p>
   <p data-lake-id="u3e683df8" id="u3e683df8"><span data-lake-id="u1a6d62f5" id="u1a6d62f5">此时X &amp; (2^3 - 1) 就相当于取X的2进制的最后三位数。</span></p>
   <p data-lake-id="ubd56b666" id="ubd56b666"><span data-lake-id="u409ab640" id="u409ab640"> </span></p>
   <p data-lake-id="u565c7533" id="u565c7533"><span data-lake-id="u6495a1b4" id="u6495a1b4">从2进制角度来看，X / 8相当于 X &gt;&gt; 3，即把X右移3位，此时得到了X / 8的商，而被移掉的部分(后三位)，则是X % 8，也就是余数。</span></p>
  </blockquote>
  <p data-lake-id="uc5ca888e" id="uc5ca888e"><br></p>
  <p data-lake-id="u4f90b42d" id="u4f90b42d"><span data-lake-id="uedd00e20" id="uedd00e20">上面的解释不知道你有没有看懂，没看懂的话其实也没关系，你只需要记住这个技巧就可以了。或者你可以找几个例子试一下。</span></p>
  <p data-lake-id="ueef7a4a1" id="ueef7a4a1"><br></p>
  <blockquote data-lake-id="ua486d468" id="ua486d468">
   <p data-lake-id="u52052b78" id="u52052b78"><span data-lake-id="u16201928" id="u16201928">6 % 8 = 6 ，6 &amp; 7 = 6</span></p>
   <p data-lake-id="ud54a294c" id="ud54a294c"><span data-lake-id="ubf0037e8" id="ubf0037e8"> </span></p>
   <p data-lake-id="u3e4c0eaa" id="u3e4c0eaa"><span data-lake-id="u26eb87d1" id="u26eb87d1">10 % 8 = 2 ，10 &amp; 7 = 2</span></p>
  </blockquote>
  <p data-lake-id="uca9dce6f" id="uca9dce6f"><br></p>
  <p data-lake-id="u56ffcad5" id="u56ffcad5"><span data-lake-id="u90394e78" id="u90394e78">​</span><img src="http://www.hollischuang.com/wp-content/uploads/2018/03/640-1.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_12%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="uc0be056d" id="uc0be056d"><br></p>
  <p data-lake-id="uaa18b089" id="uaa18b089"><span data-lake-id="u20db94fd" id="u20db94fd">所以，</span><code data-lake-id="ua6e564f3" id="ua6e564f3"><span data-lake-id="u27561e79" id="u27561e79">return h &amp; (length-1);</span></code><span data-lake-id="u21ee0691" id="u21ee0691">只要保证length的长度是</span><code data-lake-id="ubd8298bc" id="ubd8298bc"><span data-lake-id="u14db6695" id="u14db6695">2^n</span></code><span data-lake-id="u4873bad4" id="u4873bad4">的话，就可以实现取模运算了。而HashMap中的length也确实是2的幂，初始值是16，之后每次扩充为原来的2倍。</span></p>
  <p data-lake-id="u69589c33" id="u69589c33"><span data-lake-id="uaae8b7f6" id="uaae8b7f6">​</span><br></p>
  <p data-lake-id="ud3a66607" id="ud3a66607"><br></p>
  <p data-lake-id="uf664ba3b" id="uf664ba3b"><span data-lake-id="ub20d3a62" id="ub20d3a62">总结一下，HashMap的数据是存储在链表数组里面的。在对HashMap进行插入/删除等操作时，都需要根据K-V对的键值定位到他应该保存在数组的哪个下标中。而这个通过键值求取下标的操作就叫做哈希。HashMap的数组是有长度的，Java中规定这个长度只能是2的幂，初始值为16。简单的做法是先求取出键值的hashcode，然后在将hashcode得到的int值对数组长度进行取模。为了考虑性能，Java总采用按位与操作实现取模操作。</span></p>
  <p data-lake-id="u131231cb" id="u131231cb"><br></p>
  <p data-lake-id="u83cdf96e" id="u83cdf96e"><span data-lake-id="u580b97e6" id="u580b97e6">其实，使用位运算代替取模运算，除了性能之外，还有一个好处就是可以很好的解决负数的问题。因为我们知道，hashcode的结果是int类型，而int的取值范围是-2^31 ~ 2^31 - 1，即[ -2147483648, 2147483647]；这里面是包含负数的，我们知道，对于一个负数取模还是有些麻烦的。如果使用二进制的位运算的话就可以很好的避免这个问题。首先，不管hashcode的值是正数还是负数。length-1这个值一定是个正数。那么，他的二进制的第一位一定是0（有符号数用最高位作为符号位，“0”代表“+”，“1”代表“-”），这样里两个数做按位与运算之后，第一位一定是个0，也就是，得到的结果一定是个正数。</span></p>
  <h2 data-lake-id="GeWQX" id="GeWQX"><span data-lake-id="u8234dad5" id="u8234dad5">扰动计算</span></h2>
  <p data-lake-id="u905fa709" id="u905fa709"><br></p>
  <p data-lake-id="u286784e1" id="u286784e1"><span data-lake-id="ufb7d0f25" id="ufb7d0f25">其实，无论是用取模运算还是位运算都无法直接解决冲突较大的问题。</span></p>
  <p data-lake-id="u6c33d6a9" id="u6c33d6a9"><span data-lake-id="u7ad90e9f" id="u7ad90e9f">​</span><br></p>
  <p data-lake-id="u42423575" id="u42423575"><span data-lake-id="u01591b78" id="u01591b78">比如：</span><code data-lake-id="u09b86c4b" id="u09b86c4b"><span data-lake-id="ub2909561" id="ub2909561">CA11 0000</span></code><span data-lake-id="uacc22d86" id="uacc22d86">和</span><code data-lake-id="u461a9a64" id="u461a9a64"><span data-lake-id="udc4297f9" id="udc4297f9">0001 0000</span></code><span data-lake-id="uf8ef5d64" id="uf8ef5d64">在对</span><code data-lake-id="ufb945d7c" id="ufb945d7c"><span data-lake-id="ubd3d9350" id="ubd3d9350">0000 1111</span></code><span data-lake-id="u1fef3c67" id="u1fef3c67">进行按位与运算后的值是相等的。 </span></p>
  <p data-lake-id="u955f7d34" id="u955f7d34"><img src="http://www.hollischuang.com/wp-content/uploads/2018/03/640-2.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_12%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"><span data-lake-id="u69e013ad" id="u69e013ad">​</span></p>
  <p data-lake-id="uae4d5fe7" id="uae4d5fe7"><br></p>
  <p data-lake-id="uab0663fb" id="uab0663fb"><span data-lake-id="u050b6197" id="u050b6197">两个不同的键值，在对数组长度进行按位与运算后得到的结果相同，这不就发生了冲突吗。那么如何解决这种冲突呢，来看下Java是如何做的。</span></p>
  <p data-lake-id="ub1c7760e" id="ub1c7760e"><br></p>
  <p data-lake-id="uc1599f96" id="uc1599f96"><span data-lake-id="u939e2bf7" id="u939e2bf7">其中的主要代码部分如下：</span></p>
  <p data-lake-id="uc8147ba0" id="uc8147ba0"><br></p>
  <pre lang="java"><code>
h ^= k.hashCode();
h ^= (h &gt;&gt;&gt; 20) ^ (h &gt;&gt;&gt; 12);
return h ^ (h &gt;&gt;&gt; 7) ^ (h &gt;&gt;&gt; 4);
</code></pre>
  <p data-lake-id="ucd8a7739" id="ucd8a7739"><br></p>
  <p data-lake-id="u656dd984" id="u656dd984"><span data-lake-id="uf68f4caa" id="uf68f4caa">这段代码是为了对key的hashCode进行</span><strong><span data-lake-id="u2c14a432" id="u2c14a432">扰动计算</span></strong><span data-lake-id="ufef53b65" id="ufef53b65">，防止不同hashCode的高位不同但低位相同导致的hash冲突。简单点说，就是为了把高位的特征和低位的特征组合起来，降低哈希冲突的概率，也就是说，尽量做到任何一位的变化都能对最终得到的结果产生影响。</span></p>
  <p data-lake-id="u4604a475" id="u4604a475"><br></p>
  <p data-lake-id="u5e752a7e" id="u5e752a7e"><span data-lake-id="u373a87df" id="u373a87df">举个例子来说，我们现在想向一个HashMap中put一个K-V对，Key的值为“hollischuang”，经过简单的获取hashcode后，得到的值为“1011000110101110011111010011011”，如果当前HashTable的大小为16，即在不进行扰动计算的情况下，他最终得到的index结果值为11。由于15的二进制扩展到32位为“00000000000000000000000000001111”，所以，一个数字在和他进行按位与操作的时候，前28位无论是什么，计算结果都一样（因为0和任何数做与，结果都为0）。如下图所示。</span></p>
  <p data-lake-id="u0294e623" id="u0294e623"><br></p>
  <p data-lake-id="u3ce14fb8" id="u3ce14fb8"><span data-lake-id="u75b1ca53" id="u75b1ca53">​</span><img src="http://www.hollischuang.com/wp-content/uploads/2018/03/640-3.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_17%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="ua7da89b5" id="ua7da89b5"><br></p>
  <p data-lake-id="u889f7ffb" id="u889f7ffb"><span data-lake-id="ue0d6ad02" id="ue0d6ad02">可以看到，后面的两个hashcode经过位运算之后得到的值也是11 ，虽然我们不知道哪个key的hashcode是上面例子中的那两个，但是肯定存在这样的key，这就产生了冲突。</span></p>
  <p data-lake-id="u56a6f669" id="u56a6f669"><br></p>
  <p data-lake-id="ua6766e70" id="ua6766e70"><span data-lake-id="ubf6e5906" id="ubf6e5906">那么，接下来，我看看一下经过扰动的算法最终的计算结果会如何。</span></p>
  <p data-lake-id="uced7568b" id="uced7568b"><img src="http://www.hollischuang.com/wp-content/uploads/2018/03/640-4.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_24%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"><span data-lake-id="uab5d16a1" id="uab5d16a1">​</span></p>
  <p data-lake-id="u3f2cde97" id="u3f2cde97"><br></p>
  <p data-lake-id="u199bbc95" id="u199bbc95"><span data-lake-id="u51af5d75" id="u51af5d75">从上面图中可以看到，之前会产生冲突的两个hashcode，经过扰动计算之后，最终得到的index的值不一样了，这就很好的避免了冲突。</span></p>
  <p data-lake-id="u476ad5b4" id="u476ad5b4"><br></p>
 </body>
</html>